/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 先序遍历
// 需要返回字符串：使用nil表示空节点，存到字符串
type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	sb := &strings.Builder{}

	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			sb.WriteString("nil,")
			return
		}

		sb.WriteString(strconv.Itoa(root.Val))
		sb.WriteString(",")

		dfs(root.Left)
		dfs(root.Right)
	}

	dfs(root)
	return sb.String()
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	parts := strings.Split(data, ",")

	var build func() *TreeNode
	build = func() *TreeNode {
		if parts[0] == "nil" {
			parts = parts[1:]
			return nil
		}

		val, _ := strconv.Atoi(parts[0])
		parts = parts[1:]
		n := &TreeNode{val, build(), build()}

		return n
	}

	return build()
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */